题目描述

输入一个整数 $n$ ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：

• $1 <= n < 2^31$

注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

---

算法

(数位统计) $O(log_{10}n)$

分情况讨论
假设当前枚举到了第 i 位，left 表示 i 左边数字，right 表示 i 右边数字

1. 左边数字是 0 ~ (ab - 1)，出现次数 ab * t（假设当前枚举位右边数字的位数为 x，则 $t = 10^x$
2. 左边数字是 ab
   2.1 当前位是 0，不做处理
   2.2 当前位是 1，出现次数 right + 1
   2.3 当前位大于 1，出现次数 t

时间复杂度

两次循环枚举每一位，所以时间复杂度为 $O(log_{10}n)$。

空间复杂度

$O(1)$

C++ 代码

class Solution {
public:
    int countDigitOne(int n) {
        if (!n) return 0;
        vector<int> number;
        while (n) number.push_back(n % 10), n /= 10;
        
        int res = 0;
        // 从最高位开始枚举
        for (int i = number.size() - 1; i >= 0; i -- ) {
            // left: i 左边数字，right: i 右边数字，t: right 有几位，t 就是 10 的几次方
            int left = 0, right = 0, t = 1;
            // 求正在枚举的当前位的左边数字
            for (int j = number.size() - 1; j > i; j -- ) left = left * 10 + number[j];
            // 求正在枚举的当前位的右边数字
            for (int j = i - 1; j >= 0; j -- ) right = right * 10 + number[j], t *= 10;
            
            // 1. 左边数字是 0 ~ (ab - 1)
            res += left * t;
            // 2. 左边数字是 ab
            // 2.1 当前位是 0，不做处理
            // 2.2 当前位是 1
            if (number[i] == 1) res += right + 1;
            // 2.3 当前位大于 1
            else if (number[i] > 1) res += t;
        }
        
        return res;
    }
};